#pragma once

/*https://leetcode.cn/problems/intervals-between-identical-elements/
* 2121. 相同元素的间隔之和
*/

//思路：遍历一次，记录每个数据，以及对应的下标，进行分组；然后按组进行计算下标的距离

#include "../Base/CommTool.h"
#include <unordered_map>

namespace Solution_2121
{
    class Solution
    {
    public:
        //时间复杂度太大，
        //官方题解中使用的是数学方法，减少遍历次数
        vector<long long> getDistances(vector<int> &arr)
        {
            size_t size = arr.size();
            vector<long long> result(size, 0);

            unordered_map<int, vector<size_t>> groups;

            for(size_t i = 0; i<arr.size(); ++i)
            {
                auto it = groups.find(arr[i]);
                if(it == groups.end())
                {
                    groups.emplace(arr[i], vector<size_t>{i});
                }
                else
                {
                    it->second.emplace_back(i);
                }
            }

            for(const auto& group: groups)
            {
                calcByGroup(group.second, result);
            }

            return result;
        }

    private:
        void calcByGroup(const vector<size_t>& group, vector<long long>& result)
        {
            for(size_t i=0; i<group.size(); ++i)
            {
                long long count=0;
                for(size_t j=0; j<group.size() ; ++j)
                {
                    if(j == i)
                        continue;
                    count += abs((long long)group[j] - (long long)group[i]);
                }
                result[group[i]] = count;
            }
        }
    };

    void Test()
    {
        Solution solv;

        vector<int> arr{2,1,3,1,2,3,3};

        PrintVector(solv.getDistances(arr));

        arr = {10,5,10,10};
        PrintVector(solv.getDistances(arr));
    }
}